#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STR_LEN 16

int minnum(int n1, int n2, int n3)
{
    int ret = (n1 < n2 ? n1:n2);
    ret = (ret < n3 ? ret:n3);
    return ret;
}

/*
Desc: convert the distance value to percent
Input: d is the distance, len is the longer string's length
Output: none
Return: the similar percent, between 0~100
*/
int Distance2Percent(int d, int len)
{
    return (int)((1-((float)d/(float)len))*100);
}

/*
Desc: calculate the distance and similar percent
Input: s1 and s2 are string to be compared
Output: none
Return: <0 if fail, >=0 if success
*/
int LevenshteinDistance(char *s1, char *s2)
{
    int ret = -1;
    int i = 0, j = 0;
    int row = 0, col = 0;
    int len1 = 0, len2 = 0;
    int temp = 0;
    unsigned char *pMatrix = NULL;
    
    if((NULL == s1) || (NULL == s2))
    {
        printf("NULL string\n");
        return -1;
    }
    
    len1 = strlen(s1);
    len2 = strlen(s2);
    
    if(len1 == 0)
    {
        return Distance2Percent(len2, len2);
    }
    if(len2 == 0)
    {
        return Distance2Percent(len1, len1);
    }
    
    row = len1+1;
    col = len2+1;
    pMatrix = (unsigned char *)malloc(row*col);
    if(NULL == pMatrix)
    {
        printf("malloc error\n");
        return -1;
    }
    
    /* init matrix*/
    pMatrix[0] = 0; /* pMatrix[0][0] */
    for(i=1; i<row; i++)
    {
        pMatrix[0*row + i] = i;  /* pMatrix[0][i] */
    }
    for(j=1; j<col+1; j++)
    {
        pMatrix[j*col + 0] = j; /* pMatrix[j][0] */
    }
    
    for(i=0; i<len1; i++)
    {
        row = i+1; /* row index */
        for(j=0; j<len2; j++)
        {
            temp = (s1[i]==s2[j]?0:1);
            col = j+1; /* col index */
            pMatrix[row*(len1+1) + col] = minnum(pMatrix[(row-1)*(len1+1) + col]+1, pMatrix[row*(len1+1) + (col-1)]+1, pMatrix[(row-1)*(len1+1) + (col-1)]+temp);
        }
    }
    
    /* print the result */
    for(i=0; i<len1+1; i++)
    {
        for(j=0; j<len2+1; j++)
        {
            printf("%d  ", pMatrix[i*(len1+1) + j]);
        }
        printf("\n");
    }
    
    printf("\n");
    
    return Distance2Percent(pMatrix[len1*(len1+1) + len2], len1>len2?len1:len2);
}

int main()
{
    char s1[STR_LEN], s2[STR_LEN];
    
    printf("Please input s1:\n");
    scanf("%s", s1);
    printf("Please input s2:\n");
    scanf("%s", s2);
    
    printf("Similar percent %d%%\n", LevenshteinDistance(s1, s2));
    
	return 0;
}